import java.util.Scanner;
class Node {
    long value;
    Node next;
    public Node(long value) {
        this.value = value;
        this.next = null;
    }
}
public class lianbiao {
   private static Node head;  // 链表头结点
   private static int length; // 初始化链表长度为0
   public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 输出菜单选项
    System.out.println("please select the operation you want:");
    System.out.println("1. 创建");
    System.out.println("2. 插入");
    System.out.println("3. 删除");
    System.out.println("4. 顺序查找");
    System.out.println("5. 折半查找");
    System.out.println("6. 倒置");
    System.out.println("7. 输出");
    System.out.println("8. 清空");
    System.out.println("9. 排序");
    System.out.println("0. 退出");
    boolean flag = false; // 标记是否退出程序
    while (!flag) {
        System.out.print(">>>请选择你的操作:");
        int choice = scanner.nextInt();
        switch (choice) {
            case 1: // 创建链表
                System.out.print("请输入要创建的链表长度(>1):");
                int listLength = scanner.nextInt();
                System.out.print("请输入" + listLength + "个数(空格隔开,可无序输入):");
                for (int i = 0; i < listLength; i++) {
                    long value = scanner.nextInt();  // 读取用户输入的每个元素值
                    insertAtEnd(value); // 插入到链表末尾
                }
                head = insertionSort(head); // 对链表进行排序
                System.out.println("创建成功!");
                System.out.print("当前链表所有元素:");
                traverseList(); // 输出链表的所有元素
                break;
            case 2: // 插入元素
                System.out.print("请输入要插入的位置(从1开始)及元素:");
                int index = scanner.nextInt() - 1;
                long element = scanner.nextInt();
                if (insertElement(index, element)) {
                    System.out.println("插入成功!!!");
                }
                System.out.print("当前链表所有元素:");
                traverseList(); // 输出链表的所有元素
                break;
           case 3: // 删除元素
               System.out.print("请输入要删除的位置(从1开始):");
               index = scanner.nextInt() - 1;
               if (deleteElement(index) != 0) {
                   System.out.println("删除成功!!!");
               }
               System.out.print("当前链表所有元素:");
               traverseList(); // 输出链表的所有元素
               break;
           case 4: // 顺序查找
               System.out.print("请输入要查找的值:");
               element = scanner.nextInt();
               int site = sequentialSearch(element);
               if (site != -1) {
                   System.out.println("该元素位置为:" + (site + 1));
               } else {
                        System.out.println("未找到该元素!");
               }
               break;
           case 5: // 折半查找
               System.out.print("请输入要查找的值:");
               element = scanner.nextInt();
               Node foundNode = binarySearch(element);
               if (foundNode!= null) {
                   site = indexOf(foundNode);  // 找到节点的位置
                   System.out.println("该元素位置为:" + (site + 1));
               } else  {
                   System.out.println("未找到该元素!");
               }
               break;
           case 6: // 倒置
               reverseList();
               System.out.println("倒置成功!");
               System.out.print("当前链表所有元素:");
               traverseList(); // 输出链表的所有元素
               break;
           case 7: // 输出
               System.out.print("当前链表所有元素:");
               traverseList(); // 输出链表的所有元素
               break;
           case 8: // 清空
               clearList();
               System.out.println("清空成功!");
               break;
           case 9: // 排序
               head = insertionSort(head); // 对链表进行排序
               System.out.println("排序成功!!!");
               System.out.print("当前链表所有元素:");
               traverseList(); // 输出链表的所有元素
               break;
           case 0: // 退出
               flag = true;
               System.out.println("退出成功!");
               return;
           default:
               System.out.println("输入错误!");
               break;
        }
    }
}
    // 在链表末尾插入元素
public static void insertAtEnd(long value) {
       Node newNode = new Node(value); // 创建新节点
       if (head == null) {
           head = newNode; // 如果链表为空，将新节点设为头节点
       } else {
       Node current = head;
       while (current.next != null) {
           current = current.next; // 找到链表末尾
       }
       current.next = newNode; // 将新节点插入到链表末尾
    }
    length++; // 更新链表长度
}
    // 在指定位置插入元素
public static boolean insertElement(int index, long value) {
       if (index < 0 || index > length) { // 检查插入位置是否合法
           System.out.println("下标错误");
           return false;
       }
       Node newNode = new Node(value); // 创建新节点
    if (index == 0) {
        newNode.next = head; // 将新节点的next指向当前头节点
        head = newNode; // 将新节点设为头节点
    } else {
        Node current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next; // 找到插入位置前一个节点
        }
        newNode.next = current.next; // 将新节点的next指向当前节点的next
        current.next = newNode; // 将当前节点的next指向新节点
    }
    length++; // 更新链表长度
    return true;
}
// 删除元素
public static long deleteElement(int index) {
       if (index < 0 || index >= length) { // 检查删除位置是否合法
           System.out.println("下标错误");
           return 0;
       }
       Node current = head;
       long element;
       if (index == 0) {
           element = head.value; // 获取头节点的值
           head = head.next; // 将头节点设为下一个节点
       } else {
           for (int i = 0; i < index - 1; i++) { // 找到删除位置前一个节点
               current = current.next;
           }
           element = current.next.value; // 获取要删除节点的值
           current.next = current.next.next; // 将要删除节点的前一个节点的next指向要删除节点的后一个节点
       }
       length--; // 更新链表长度
    return element;
}
// 遍历链表
public static void traverseList() {
       Node current = head;
       while (current != null) {
           System.out.print(current.value + " "); // 输出链表中的每个元素
           current = current.next;
       }
     System.out.println();
}
// 清空链表
public static void clearList() {
       head = null; // 将头节点设为null
       length = 0; // 更新链表长度为0
}
// 顺序查找
public static int sequentialSearch(long element) {
       Node current = head;
       int index = 0;
       while (current != null) {
           if (current.value == element) return index; // 如果找到元素，返回其位置
           current = current.next;
           index++;
       }
     return -1; // 未找到返回-1
}
// 折半查找
static Node binarySearch(long element) {
       head = insertionSort(head); // 首先对链表进行排序
       Node left = head;
       Node right ; // 找到链表的最后一个节点
       Node current = head;
       while (current != null && current.next != null) {
           current = current.next;
       }
       right = current; // 折半查找循环条件
       while (left != null) {
           Node mid = getMiddle(left, right); // 找到中间节点
           if (mid.value == element) {
               return mid; // 如果找到元素，返回其节点
           } else if (mid.value < element) {
               left = mid.next; // 如果中间节点的值小于要查找的值，搜索右半部分
           } else {
               if (mid == left) {
                   return null; // 防止无限循环
               }
               right = mid; // 如果中间节点的值大于要查找的值，搜索左半部分
            }
        }
     return null; // 未找到返回null
}
    // 倒置链表
public static void reverseList() {
       Node previous = null; // 初始化前一个节点为null
       Node current = head;
       Node next;
       while (current != null) {
           next = current.next; // 获取当前节点的下一个节点
           current.next = previous; // 将当前节点的next指向前一个节点
           previous = current; // 将之前节点设为当前节点
           current = next; // 将当前节点设为下一个节点
       }
     head = previous; // 将头节点设为之前节点（即原链表的最后一个节点）
}
// 获取节点的索引
static int indexOf(Node node) {
       Node current = head;
       int index = 0;
       while (current != null) {
           if (current == node) {
               return index; // 遍历链表，查找节点的位置
           }
           current = current.next;
           index++;
       }
       return -1;
}
// 找到中间节点
static Node getMiddle(Node left, Node right) {
       Node slow = left;
       Node fast = left;
       while (fast != right && fast.next != right) {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;
}
// 插入排序
static Node insertionSort(Node head) {
       Node sorted = null; // 初始化已排序链表为空
       Node current = head;
       while (current != null) { // 遍历链表，对每个节点进行插入排序
           Node next = current.next; // 获取当前节点的下一个节点
           sorted = sortedInsert(sorted, current); // 将当前节点插入到已排序链表中
           current = next; // 将当前节点设为下一个节点
       }
       return sorted; // 返回已排序链表的头节点
}
// 插入排序的辅助方法
static Node sortedInsert(Node head, Node newNode) {
       if (head == null || head.value >= newNode.value) { // 如果已排序链表为空或新节点的值小于等于头节点的值
           newNode.next = head; // 将新节点的next指向头节点
           head = newNode; // 将新节点设为头节点
       } else {
           Node current = head;
           while (current.next != null && current.next.value < newNode.value) {  // 找到新节点应插入的位置
               current = current.next;
           }
           newNode.next = current.next; // 将新节点的next指向current的next
           current.next = newNode; // 将current的next指向新节点
       }
       return head;
    }
}
